#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <unordered_map>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode *next;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class inorderQuick {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        // morris算法，每次记录下子中序列的最后一个节点为predecessor，然后将其指向root
        vector<int> res;
        TreeNode* curNode = root;
        TreeNode* predecessor = nullptr;
        
        while (curNode != nullptr) {
            if (curNode->left == nullptr) {
                // 左子树为空，进入右子树
                res.push_back(curNode->val);
                curNode = curNode->right;
            }
            else {
                // 左子树不为空
                predecessor = curNode->left;
                // 找到左子树中序列末尾节点
                while (predecessor->right != nullptr && predecessor->right != curNode)
                    predecessor = predecessor->right;
                // 末尾节点右子树为空（未曾遍历过），则将其right设为curNode
                if (predecessor->right == nullptr) {
                    predecessor->right = curNode;
                    curNode = curNode->left;
                }
                // 否则（已遍历），将其断开，right置空
                else {
                    res.push_back(curNode->val);
                    predecessor->right = nullptr;
                    curNode = curNode->right;
                }
            }
        }
        return res;
    }

    vector<int> stackInorder(TreeNode* root) {
        vector<int> res;
        stack<TreeNode *> stk;
        TreeNode* curNode = root;

        while (curNode != nullptr || !stk.empty()) {
            while (curNode != nullptr) {
                stk.push(curNode);
                curNode = curNode->left;
            }
            curNode = stk.top();
            stk.pop();
            res.push_back(curNode->val);
            curNode = curNode->right;
        }

        return res;
    }
};

class flattenInorder {
public:
    TreeNode* increasingBST(TreeNode* root) {
        TreeNode* res = new TreeNode(-1);
        prev = res;
        inorder(root);
        return res->right;
    }

    void inorder(TreeNode* root) {
        if (root == nullptr)
            return;
        inorder(root->left);
        root->left = nullptr;
        prev->right = root;
        prev = root;
        inorder(root->right);
    }
private:
    TreeNode* prev;
};